import collections
class Solution(object):
    def maximalPathQuality(self, values, edges, maxTime):
        d = collections.defaultdict(dict)
        for u, v, t in edges:
            d[u][v] = t
            d[v][u] = t
        n = len(values)
        st = [0] * n
        self.ans = 0
        def dfs(node, t, val):
            flag = False
            if st[node] == 0:
                next_val = values[node] + val
                st[node] = 1
                flag = True
            else:
                next_val = val
            if node == 0:
                self.ans = max(self.ans, next_val)
            for v in d[node]:
                if t >= d[node][v]:
                    dfs(v, t - d[node][v], next_val)
            if flag:
                st[node] = 0
        dfs(0, maxTime, 0)
        return self.ans
                


data = Solution()
values = [0,32,10,43]
edges = [[0,1,10],[1,2,15],[0,3,10]]
maxTime = 49
print(data.maximalPathQuality(values, edges, maxTime))